package leetcode_周赛._2024._04;

import java.util.Arrays;

/**
 * 第 394 场周赛 AC_2
 *
 * @author yezh
 * @date 2024/4/21 19:14
 */
public class _21 {

    public static void main(String[] args) {
        int[][] grid = {{1, 0, 2}, {1, 0, 2}};
        new _21().minimumOperations(grid);
    }

    /**
     * 3122.使矩阵满足条件的最少操作次数
     * 算法：记忆化搜索、动态规划
     * 每一列的值相等, 相邻两列的值不相等
     * 要点：只需要每列能够保留的最大数量和次大数量即可
     */
    public int minimumOperations(int[][] grid) {
        // 每一列能够保留的最大数量
        int m = grid.length, n = grid[0].length;
        int[][] cnt = new int[n][10];
        for (int j = 0; j < n; j++) for (int i = 0; i < m; i++) cnt[j][grid[i][j]]++;
        // 从后往前遍历每一列, 把每种情况都枚举一遍
        int[][] memo = new int[n][11];
        for (int i = 0; i < n; i++) Arrays.fill(memo[i], -1);
        return m * n - dfs(n - 1, 10, memo, cnt);
    }

    int dfs(int col, int pre, int[][] memo, int[][] cnt) {
        if (col < 0) return 0;
        if (memo[col][pre] != -1) return memo[col][pre];
        int max = 0;
        for (int i = 9; i >= 0; i--)
            if (i != pre) max = Math.max(max, cnt[col][i] + dfs(col - 1, i, memo, cnt));
        return memo[col][pre] = max;
    }

    public int minimumOperations_dynamic(int[][] grid) {
        // 每一列能够保留的最大数量
        int m = grid.length, n = grid[0].length;
        int[][] cnt = new int[n][10];
        for (int j = 0; j < n; j++) for (int i = 0; i < m; i++) cnt[j][grid[i][j]]++;
        // f0 - 在列值为 pre 时保留的最大值(即不需要修改的次数), f1 - 在列值不为 pre 时保留的最大值
        int f0 = 0, f1 = 0, pre = -1;
        for (int j = 0; j < n; j++) {
            int mx, mx0 = 0, mx1 = 0, x = 0;
            for (int k = 0; k < 10; k++) {
                // 假设当前列取都设为 k, 如果 k 与前一列不相等, 则取 f0
                mx = cnt[j][k] + (k != pre ? f0 : f1);
                if (mx > mx0) {
                    mx1 = mx0;
                    mx0 = mx;
                    x = k;
                } else if (mx > mx1) mx1 = mx;
            }
            f0 = mx0;
            f1 = mx1;
            pre = x;
        }
        return m * n - f0;
    }

}
